package com.example.demo.huawei;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

/**
 * 构成指定长度字符串个数
 * M（0-30）个字符 从中取出任意字符 每个字符只能用一次
 * 拼接成长度为n （o<n<=5）的字符串
 * 要求相同字符不可以相邻
 * <p>
 * 计算总共可以拼接出多少种满足条件的字符串
 * 非法输入等其他情况返回0
 */
public class Main27 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] input = scanner.nextLine().split("\\s");
        String str = input[0];
        int n = Integer.parseInt(input[1]);
        //        System.out.println(str);
        //        System.out.println(n);
        // aab 2
        // 如果不考虑 相同字符相邻情况 这是排列问题
        permute(str, n);
    }

    static void permute(String s, int n) {
        List<List<Character>> res = new ArrayList<>();
        dfs(s.toCharArray(), new boolean[s.length()], new LinkedList<>(), res, n, '\0');
        //        System.out.println(res);
        System.out.println(res.size());
    }

    static void dfs(char[] array, boolean[] visited, LinkedList<Character> list, List<List<Character>> res, int n, char lastChar) {
        // 递归终止条件
        if (list.size() == n) {
            res.add(new ArrayList<>(list));
            return;
        }
        // aab 2
        for (int i = 0; i < array.length; i++) {
            if (i > 0 && array[i] == array[i - 1] && !visited[i - 1]) {
                continue;
            }
            if (visited[i] || (list.size() > 0 && array[i] == lastChar)) {
                continue;
            }
            char c = array[i];
            if (!visited[i]) {
                list.push(c);
                visited[i] = true;
                System.out.println("递归之前 => " + list);

                dfs(array, visited, list, res, n, c);
                visited[i] = false;
                list.pop();
                System.out.println("递归之后 => " + list);
            }


        }
    }
}
